#include <bits/stdc++.h>
#ifndef DEBUG
#define debug
#endif
using namespace std;
using i64 = int64_t;

void solve() {
  i64 n, k;
  cin >> n >> k;
  vector<int> a(n + 1);
  i64 total = 0;
  for (int i = 1; i <= n; i ++) {
    cin >> a[i];
    total += a[i];
  }
  sort(a.begin() + 1, a.end());
  vector<i64> sum(n + 1);
  for (int i = 1; i <= n; i ++) {
    sum[i] = sum[i - 1] + a[i];
  }
  auto query = [&](int l, int r) {
    return sum[r] - sum[l - 1];
  };
  i64 ans = 0;
  auto calc = [&](int hi, i64 x, i64 i) -> i64 {
    auto get = [&](int len) {
      i64 res = 0;
      res -= query(i + 1, min(i + len, n));
      res -= query(1, min(len * k, i - 1));
      res += x * (len + min(len * k, i - 1));
      return res;
    };
    i64 mx = get(1);
    int lo = 2;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      if (get(mid) >= get(mid - 1)) lo = mid + 1;
      else hi = mid - 1;
    }
    return max(mx, get(hi));
  };
  for (i64 i = 2; i < n; i ++) {
    ans = max(ans, calc(min(i - 1, n - i), a[i], i));
  }
  cout << total + ans << '\n';
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int T = 1;
  cin >> T;
  for (int cas = 1; cas <= T; cas ++) {
    // cout << "Case #" << cas << ": ";
    solve();
  }
}